Skip to main content

How to Avoid Fighting Rust Borrow Checker

The 3 important facts in Rust:

  • Tree-shaped ownership. In Rust's ownership system, one object can own many children or no chlld, but must be owned by exactly one parent. Ownership relations form a tree. 1
  • Mutable borrow exclusiveness. If there exists one mutable borrow for an object, then no other borrow to that object can exist. Mutable borrow is exclusive.
  • Borrow is contagious (if crossing function boundary). If you borrow a child, you indirectly borrow the parent (and parent's parent, and so on). Just borrowing one wheel of a car makes you borrow the whole car. Combined with previous point, it can cause troubles for mutable data. It can be avoided by split borrow, but not across functions.

Note that Rust borrow checker can reject some incorrect programs but also reject some correct programs.

Considering reference shape​

Firstly consider the reference 2 shape of your in-memory data.

  • If the reference is tree-shaped, then it's simple and natural in Rust.
  • If the reference shape has sharing, things become a little complicated.
    • Sharing means there are two or more references to the same object.
    • If shared object is immutable:
      • If the sharing is scoped (only temporarily shared), then you can use immutable borrow. You may need lifetime annotation.
      • If the sharing is not scoped (may share for a long time, not bounded within a scope), you need to use reference counting (Rc in singlethreaded case, Arc in possibly-multithreaded case)
    • If shared object is mutable, then it's in borrow-check-unfriendly case. Solutions elaborated below.
    • Contagious borrow can cause unwanted sharing (elaborated below).
  • If the reference shape has cycle, then it's also in borrow-check-unfriendly case. Solutions elaborated below.

The most fighting with borrow checker happens in the borrow-check-unfriendly cases.

Summarize solutions​

The solutions in borrow-checker-unfriendly cases (will elaborate below):

  • Data-oriented design. Avoid unnecessary getter and setter. Avoid contagious borrow. Do split borrow if necessary.
  • Use ID/handle to replace borrow.
  • Defer mutation. Turn mutation as commands and execute later.
  • Avoid mutation. Mutate-by-recreate. Use Arc to share immutable data.
  • For circular reference:
    • For graph data structure, use ID/handle to replace borrow.
    • For callback, use event bus or Arc<QCell<T>> (use Weak to cut cycle)
  • Make borrows as shortest as possible, as temporary as possible.
  • Arc<RwLock<T>> (only use when really necessary)
  • unsafe and raw pointer (only use when really necessary)

Contagious borrow issue​

The previously mentioned two important facts:

  • Mutable borrow exclusiveness. If you mutable borrow it, others cannot borrow it.
  • Borrow is contagious. Just borrowing one wheel of a car makes you borrow the whole car, if the borrow crosses function boundary. (unless using split borrow that works within one scope)

A simple example: 3

pub struct Parent {  
    total_score: u32,  
    children: Vec<Child>  
}
pub struct Child {  
    score: u32  
}

impl Parent {  
    fn get_children(&self) -> &Vec<Child> {  
        &self.children  
    }  
  
    fn add_score(&mut self, score: u32) {  
        self.total_score += score;  
    }  
}

fn main() {  
    let mut parent = Parent{total_score: 0, children: vec![Child{score: 2}]};  
  
    for child in parent.get_children() {  
        parent.add_score(child.score);  
    }
}

Compile error:

25 |     for child in parent.get_children() {
   |                  ---------------------
   |                  |
   |                  immutable borrow occurs here
   |                  immutable borrow later used here
26 |         parent.add_score(child.score);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

This code is totally memory-safe: the .add_score() only touch the total_score field, and .get_children() only touch the children field. They work on separate data, they still clashes, because of contagious borrow:

  • In fn get_children(&self) -> &Vec<Child> { &self.children }, although the method body just borrows children field, the return value indirectly borrows the whole self, not just one field.
  • In fn add_score(&mut self, score: u32) { self.total_score += score; }, the function body only mutably borrowed total_score field, but the argument &mut self borrows the whole Parent, not just one field.
  • Inside the loop, one immutable borrow to the whole Parent and one mutable borrow to the whole Parent overlaps in lifetime.

The core problem is that you just want to borrow one field, but forced to borrow the whole object.

What if I just inline get_children and add_score? Then it compiles fine:

pub struct Parent {  
    total_score: u32,  
    children: Vec<Child>  
}
pub struct Child {  
    score: u32  
}
fn main() {  
    let mut parent = Parent{total_score: 0, children: vec![Child{score: 2}]};  
  
    for child in &parent.children {  
        let score = child.score;  
        parent.total_score += score;  
    }  
}

Why that compiles? Because it does a split borrow: the compiler sees borrowing of individual fields in one function (main()), and don't do contagious borrow.

The deeper cause is that:

  • Borrow checker works locally: when seeing a function call, it only checks function signature, instead of checking code inside the function. (Its benefit is to make borrow checking faster and simpler. Doing whole-program analysis is hard and slow, and doesn't work with things like dynamic linking.)
  • Information is lost in function signature: the borrowing information becomes coarse-grained and is simplified in function signature. The type system does not allow expressing borrowing only one field, and can only express borrowing the whole object. There are propsed solutions.

The solutions:

  • Avoid OOP-style getter and setter (just make fields public), unless necessary.
    • Data-oriented design (DOD). Just directly work on data and make fields public.
    • If you design a library and want encapsulation, it's recommended to use ID/handle to replace borrow (elaborated below).
    • The getter that returns cloned/copied value is fine. If data is immutable, getter is also usually fine.
  • Use ID/handle to replace borrow.
  • Make borrow as shortest as possible.
  • Other workarounds like Arc<QCell<T>> Arc<RwLock<T>>, etc.
  • Avoid mutation or defer mutation:

Avoid mutation​

The previous problem occurs partially due to mutable borrow exclusiveness. If all borrows are immutable, then contagious borrow is usually not a problem.

The common way of avoiding mutation is mutate-by-recreate: All data is immutable. When you want to mutate something, you create a new version of it. Just like in pure functional language (e.g. Haskell).

Unfortunately, mutate-by-recreate is also contagious: if you recreated a new version of a child, you need to also recreate a new version of parent that holds the new child, and parent's parent, and so on. There are abstractions like lens to make this kind of cascade-recreate more convenient.

Mutate-by-recreate can be useful for cases like:

  • Safely sharing data in multithreading (read-copy-update (RCU), copy-on-write (COW))
  • Take snapshot and rollback efficiently

Mutate-by-recreate can be optimized by sharing unchanged sub-structures. See also: Persistent data structure, Rope.

Defer mutation. Mutation-as-data​

Another solution is to treat mutation as data. To mutate something, append a mutation command into command queue. Then execute the mutation commands at once. (Note that command should not indirectly borrow base data.)

  • In the process of creating new commands, it only do immutable borrow to base data, and only one mutable borrow to the command queue at a time.
  • When executing the commands, it only do one mutable borrow to base data, and one borrow to command queue at a time.

What if I need the latest state before executing the commands in queue? Then inspect both the command queue and base data to get latest state (LSM tree does similar things). You can often avoid needing to getting latest state during processing, by separating it into multiple stages.

Treating mutation as data also has other benefits:

  • The mutation can be serialized, and sent via network or saved to disk.
  • The mutation can be inspected for debugging and logging.
  • You can post-process the command list, such as sorting, filtering. If the data is sharded, the mutation command can dispatch to specific shard.
  • Transactional databases often use write-ahead log (WAL) to help atomicity of transactions. Database writs all mutations into WAL. Then after some time the mutations in WAL will be merged to base data in disk. Database often keep the latest mutated data in memory for querying.
  • Event sourcing. Derive the latest state from events and previous checkpoint. Distributes systems often use consensus protocol (like Raft) to replicate log (events, mutations). The mutable data is derived from logs and previous checkpoint.
  • The idea of turning operations into data is also adopted by io_uring and modern graphics APIs (Vulkan, Metal, WebGPU).
  • The idea of turning mutation into insertion is also adopted by ClickHouse. In ClickHouse, direct mutaiton is not performant. Mutate-by-insert is faster, but querying require aggregate both the old data and new mutations.

The previous code rewritten using deferred mutation:

pub struct Parent {  
    total_score: u32,  
    children: Vec<Child>  
}  
pub struct Child {  
    score: u32  
}  
pub enum Command {  
    AddTotalScore(u32),  
    // can add more kinds of commands  
}  
  
impl Parent {  
    fn get_children(&self) -> &Vec<Child> {  
        &self.children  
    }  
  
    fn add_score(&mut self, score: u32) {  
        self.total_score += score;  
    }  
}  
  
fn main() {  
    let mut parent = Parent{total_score: 0, children: vec![Child{score: 2}]};  
    let mut commands: Vec<Command> = Vec::new();  
  
    for child in parent.get_children() {  
        commands.push(Command::AddTotalScore(child.score));  
    }  
  
    for command in commands {  
        match command {  
            Command::AddTotalScore(num) => {  
                parent.add_score(num);  
            }  
        };  
    }  
}

About circular reference​

Circular reference in mathematics​

Some may argue that "Circular reference is a bad thing. Look how much trouble do circular references create in mathematics":

Details

  • Circular proof: if A then B, if B then A. Circular proof is wrong. It can prove neither A nor B.

  • The set that indirectly includes itself cause Russel's paradox: Let R be the set of all sets that are not members of themselves. R contains R deduces R should not contain R, and vice versa. Set theory carefully avoids cirular reference.

  • Halting problem is proved impossible to solve, by using circular reference:

    Assume there exists a function halts(program, input), which takes in a program and input data, and outputs a boolean telling whether program(input) will eventually halt.

    Then construct a paradox program paradox:

fn paradox(program: Program) {
    if halts(program, program) {
        while true {} // dead loop
    } else {
        return; // halts
    }
}

Then halts(paradox, paradox) will cause a paradox. If it returns true, then paradox(paradox) halts, but in paradox's definition it should deadloop.

Rice's theorem is an extension to Halting problem: All non-trivial semantic properties of programs are undecidable (includes whether it eventually halts).

  • Gödel's incomplete theorem.
    • Firstly encode symbols, statements and proofs into data 4. The statements that contain free variables (e.g. x is a free variable in "x is an even number") can also be encoded (it can represent "functions" and even "higher-order functions").
    • is_proof(theory, proof) allows determining whether a proof successfully proves a theory.
    • Then provable(theory) is defined as whether there exists a proof that satisfies is_proof(theory, proof).
    • Unprovable is inverse of provable: unprovable(theory) = !provable(theory)
    • Let H(x) = unprovable(x(x)). Then let G = H(H) = unprovable(H(H)) = unprovable(G) 5, which creates a self-referencial statement: G means G is not provable. If G is true, then G is not provable, then G is false, which is a paradox.

There is something in common between Halting problem, Russel's paradox and Gödel's incomplete theorem: they all self-reference and "negate" itself, causing paradox.

Circular reference in programming​

Circular reference being bad in mathematics does NOT mean they are also bad in programming. The circular reference in math theories are different to circular reference in data. There are many valid cases of circular references in programming (e.g. there are doublely-linked list running in Linux kernel that works fine).

But circular reference do add risks to memory management:

  • In C/C++, if two objects point to each other, when one object destructs, the another object's reference should be cleared, or there will be risk of use-after-free.
  • When using reference counting, loop should be cut by weak reference, or it will memory leak.
  • In GC languages, circular reference has memory leak risk. If all children references parents, and parents references children, then referencing any child will keep the whole structure alive.

Here are some common use cases of circular reference:

  • Case 1: The parent references a child. The child references its parent, just for convenience. (Referencing to parent is not necessary, parent can be passed by argument)
  • Case 2: The parent registers a callback to child. When something happened on child, the callback is called, and parent do something. It that case, parent references child, child references callback, callback references parent.
  • Case 3: In a tree structure, the child references parent allows getting the path from one node to root node. Without it, you cannot get the path from just one node reference, and need to store variable-length path information.
  • Case 4: The data is inherently a graph structure that can contain cycles.
  • Case 5: The data requires self-reference.

Avoid "just-for-convenience" circular reference in Rust​

In the case 1 above: The child references parent, just for convenience. In OOP code. If you just have a reference to a child object, and you want to use some data in parent, child referencing parent would be convenient. Without it, the parent also need to be passed as argument.

That convenience in OOP languages will lead to troubles in Rust. It's recommended to pass extra arguments instead of having circular reference.

Note that due to previously mentioned contagious borrow issue, you cannot mutably borrow child and parent at the same time (except using interior mutability). The workaround is to 1. do a split borrow on parent and pass the individual components of parent (pass more arguments and be more verbose than in other languages) 2. use interior mutability (e.g. RefCell, Mutex, QCell).

The callback circular reference​

Observer pattern is commonly used in GUI and other dynamic reactive systems. If parent want to be notified when some event happens on child, the parent register callback to child, and child calls callback when event happens.

However, the callback function object often have to reference the parent (because it need to use parent's data). Then it creates circular reference: parent references child, child references callback, callback references parent, as mentioned previously in case 2.

Solutions:

  • Use reference counting and interior mutability. The classical ones: Rc<RefCell<T>> (singlethreaded), Arc<RwLock<T>> (multithreaded). I also recommend using QCell (elaborated below): Rc<QCell<T>>, Arc<QCell<T>>.

    The back-reference (callback to parent, child to parent) should use Weak to avoid memory leak.

  • Use event bus to replace callbacks. Similar to the previous deferred mutation, we turn event into data. Each component listen to specific "event channel" or "event topic". When something happens, put the event into event bus, then event bus notifies components.

  • Use ID/handle to replace borrow (elaborated later).

The circular reference that's inherent in data structure​

In the previously mentioned case 3 and case 4, circular reference is needed in data structure.

Solutions:

  • Use reference counting and interior mutability (previously mentioned). This is recommended when there are many different types of components and you want to add new types easily (like in GUI).
  • Use ID/handle to replace borrow (elaborated later). This is recommended when you want more compact memory layout, and you rarely need to add new types into data (suitable for data-intensive cases, can obtain better performance due to cache-friendliness).

Self-reference​

Self-reference means a struct contains an interior pointer to another part of data that it owns.

Zero-cost self reference requires Pin and unsafe. Normal Rust mutable borrow allow moving the value out (by mem::replace, or mem::swap, etc.). Pin disallows that, as self-reference pointer can be invalidated by moving. They are complex and hard to use. Workarounds includes separating child and use reference counting so it's no longer self-reference.

Use handle/ID to replace borrow​

Data-oriented design:

  • Try to pack data into contagious array, (instead of objects laid out sparsely managed by allocator).
  • Use handle (e.g. array index) or ID to replace reference.
  • Decouple object ID with memory address. An ID can be saved to disk and sent via network, but a pointer cannot (the same address cannot be used in another process or after process restart, because there may be other data in the same address).
  • The different fields of the same object doesn't necessarily need to be together in memory. The one field of many objects can be put together (parallel array).
  • Manage memory based on arenas.

One kind of arena is slotmap:

  • Slotmap is basically an array of elements, but each element has a version integer.
  • Each handle (key) has an index and a version.
  • When accessing the slotmap, it firstly does a bound check, then checks version.
  • After removing element, the version increments. The previous handle cannot get the new element at the same index, because of version mismatch.
  • The handles (keys) are just Copy-able data that's not restricted by borrow checker.
  • Although memory safe, it still has the equivalent of "use-after-free": using a handle of an already-removed object cannot get element from the slotmap 6. Each get element operation may fail.
  • Note that slotmap is not efficient when there are many unused empty space between elements. Slotmap offers two other variants for sparce case.

Other map structure, like HashMap or TreeMap can also be arenas.

If no element can be removed from arena, then a Vec can also be an areana.

One important fact: when we use ID/handle to replace borrow, the borrow checker no longer ensure that the ID/handle will point to a living object.

Entity component system​

Entity component system (ECS) is a way of organizing data that's different to OOP. In OOP, an object's fields are laid together in memory. But in ECS, each object is separated into components. The same kind of components for different entities are managed together (often laid together in memory). It can improve cache-friendliness. (Note that performance is affected by many factors and depends on exact case.)

ECS also favors composition over inheritance. Inheritance tend to bind code with specific types that cannot easily compose.

(For example, in an OOP game, Player extends Entity, Enemy extends Entity. There is a special enemy Ghost that ignores collision and also extends Enemy. But one day if you want to add a new player skill that temporarily ignores collision like Ghost, you cannot make Player extend Ghost and have to duplicate code. In ECS that can be solved by just combining special collision component.)

Generalized reference and two reference semantics​

The concept of generalized reference:

  • The reference in GC languages is generalized reference.
  • Pointer is generalized reference.
  • Borrowing in Rust is generalized reference.
  • Ownership in Rust is also considered as generalized reference.
  • Smart pointer (Rc, Arc, Weak, Box in Rust, shared_ptr, weak_ptr, unique_ptr in C++, etc.) are generalized reference.
  • IDs are generalized reference. (It includes all kinds of IDs, including handles, UUID, string id (URL, file path, username, etc.), integer id, primary key, and all kinds of identification information).

The generalized reference is separated into two kinds: strong and weak:

  • Strong generalized reference: The system ensures it always points to a living object.

    It contains: normal references in GC languages (when not null), Rust borrow and ownership, strong reference counting (Rc, Arc, shared_ptr when not null), and ID in database with foreign key constraint.

  • Weak generalized reference: The system does NOT ensure it points to a living object.

    It contains: ID (no foreign key constraint), handles, weak reference in GC languages, weak reference counting (Weak, weak_ptr).

The major differences:

  • For weak generalized references, every data access may fail, and requires error handling. (just panic is also a kind of error handling)
  • For strong generalized reference, the lifetime of referenced object is tightly coupled with the existence of reference:
    • In Rust, the coupling comes from borrow checker. The borrow is limited by lifetime and other constraints.
    • In GC langauges, the coupling comes from GC. The existence of a strong reference keeps the object alive. Note that in GC languages there are live-but-unusable objects (e.g. Java FileInputStream is unusable after closing).
    • In reference counting, the coupling of course comes from runtime reference counting.
    • The foreign key constraint of ID is enforced by database.
  • For weak generalized reference, the lifetime of object is decoupled from referces to it.

If you want to design an abstraction that decouples object lifetime and how these objects are referenced, it's recommended to either:

  • Use weak generalized reference, such as ID and handle. The object can be freed without having to consider how its IDs are held.
  • Use strong generalized reference, but add a new usability state that's decoupled with object lifetime. This is common in GC languages. Examples:
    • In JS, if you send an ArrayBuffer to another web worker, the ArrayBuffer object can still be referenced and kept alive, but the binary content is no longer accessible from that ArrayBuffer object.
    • In Java, the IO-related objects (e.g. FileInputStream) can no longer be used after closing, even these objects are still referenced and still alive.

Mutable borrow exclusiveness​

As previously mentioned, Rust has mutable borrow exclusiveness:

  • A mutable borrow to one object cannot co-exist with any other borrow to the same object. Two mutable borrows cannot co-exist. One mutable and one immutable also cannot co-exist.
  • Multiple immutable borrows for one object can co-exist.

That is also called "mutation xor sharing", as mutation and sharing cannot co-exist.

In multi-threading case, this is natural: multiple threads read the same immutable data is fine. As long as one thread mutates the data, other thread cannot safely read or write it without other synchronization (atomics, locks, etc.).

But in single-threaded case, this restriction is not natural at all. No mainstream language (other than Rust) has this restriction.

Mutation xor sharing is, in some sense, neither necessary nor sufficient. It’s not necessary because there are many programs (like every program written in Java) that share data like crazy and yet still work fine. It’s also not sufficient in that there are many problems that demand some amount of sharing – which is why Rust has “backdoors” like Arc<Mutex<T>>, AtomicU32, and—the ultimate backdoor of them all—unsafe.

- The borrow checker within

Mutable borrow exclusiveness is still important for safety of interior pointer, even in single thread:

Interior pointer​

Rust has interior pointer. Interior pointer are the pointers that point into some data inside another object. A mutation can invalidate the memory layout that interior pointer points to.

For example, you can take pointer of an element in Vec. If the Vec grows, it may allocate new memory and copy existing data to new memory, thus the interior pointer to it can become invalid (break the memory layout that interior pointer points to). Mutable borrow exclusiveness can prevent this issue from happening:

fn main() {  
    let mut vec: Vec<u32> = vec!(1, 2, 3);  
    let interior_pointer: &u32 = &vec[0];  
    vec.push(4);  
    print!("{}", *interior_pointer);  
}

Compile error:

3 |     let interior_pointer: &u32 = &vec[0];
  |                                   --- immutable borrow occurs here
4 |     vec.push(4);
  |     ^^^^^^^^^^^ mutable borrow occurs here
5 |     print!("{}", *interior_pointer);
  |                  ----------------- immutable borrow later used here

Another example is about enum: interior pointer pointing inside enum can also be invalidated, because different enum variants has different memory layout. In one layout the first 8 bytes is integer, in another layout the first 8 bytes may be a pointer. Treating an arbitrary integer as a pointer is definitely not memory-safe.

enum DifferentMemoryLayout {  
    A(u64, u64),  
    B(String)  
}  
  
fn main() {  
    let mut v: DifferentMemoryLayout = DifferentMemoryLayout::A(1, 2);  
    let interior_pointer: &u64 = match v {  
        DifferentMemoryLayout::A(ref a, ref b) => {a}  
        DifferentMemoryLayout::B(_) => { panic!() }  
    };  
    v = DifferentMemoryLayout::B("hello".to_string());  
    println!("{}", *interior_pointer);  
}

Compile error:

9  |         DifferentMemoryLayout::A(ref a, ref b) => {a}
   |                                  ----- `v` is borrowed here
...
12 |     v = DifferentMemoryLayout::B("hello".to_string());
   |     ^ `v` is assigned to here but it was already borrowed
13 |     println!("{}", *interior_pointer);
   |                    ----------------- borrow later used here

Note that sometimes mutating can keep validity of interior pointer. For example, changing an element in Vec<u32> doesn't invalidate interior pointer to elements, because there is no memory layout change. But Rust by default prevents all mutation when interior pointer exists (unless using interior mutability).

Interior pointer in other languages​

Golang also supports interior pointer, but doesn't have such restriction. For example, interior pointer into slice:

package main

import "fmt"

func main() {
	slice := []int{1, 2, 3}
	interiorPointer := &slice[0]
	slice = append(slice, 4)
	fmt.Printf("%v\n", *interiorPointer)
	fmt.Printf("old interior pointer: %p  new interior pointer: %p\n", interiorPointer, &slice[0])
}

Output

1
old interior pointer: 0xc0000ac000  new interior pointer: 0xc0000ae000

Because after re-allocating the slice, the old slice still exists in memory (not immediately freed). If there is an interior pointer into the old slice, the old slice won't be freed by GC. The interior pointer will always be memory-safe (but may point to stale data).

Golang also doesn't have sum type, so there is no equivalent to enum memory layout change in the previous Rust example.

Also, Golang's doesn't allow taking interior pointer to map entry value, but Rust allows. Rust's interior pointer is more powerful than Golang's.

In Java, there is no interior pointer. So no memory safety issue caused by interior pointer.

But in Java there is one thing logically similar to interior pointer: Iterator. Mutating a container can cause iterator invalidation:

public class Main {  
    public static void main(String[] args) {  
        List<Integer> list = new ArrayList<>();  
        list.add(1);  
  
        Iterator<Integer> iterator = list.iterator();  
        while (iterator.hasNext()) {  
            Integer value = iterator.next();  
            if (value < 3) {  
                list.remove(0);  
            }  
        }  
    }  
}

That will get java.util.ConcurrentModificationException. Java's ArrayList has an internal version counter that's incremented every time it changes. The iterator code checks concurrent modification using version counter.

Even without the version check, it will still be memory-safe because array access is range-checked.

Note that the container for loop in java internally use iterator (except for raw array). Inserting or removing to the container while for looping can also cause iterator invalidation.

Note that iteration invalidation is logic error, no matter whether it's memory-safe or not.

In Java, you can remove element via the iterator, then the iterator will update together with container, and no longer invalidate. Or use removeIf that avoids managing iterator.

Mutable borrow exclusiveness is still important in single-threaded case, because of interior pointer. But if we don't use any interior pointer, then mutable borrow exclusiveness is not necessary for memory safety in single-thread case.

That's why mainstream languages has no mutable borrow exclusiveness, and still works fine in single-threaded case. Java, JS and Python has no interior pointer. Golang and C# have interior pointer, they have GC and restrict interior pointer, so memory safe is still kept without mutable borrow exclusiveness.

Rust's mutable borrow exclusiveness creates a lot of troubles in single-threaded cases. But it also has benefits (even in signle-threaded cases):

  • Make the borrow more universal. In Rust, map key and value can be borrowed. But in Golang you cannot take interior pointer to map key or value. This makes abstractions that work with borrows more general.
  • Mutable borrow is exclusive, so Rust can emit noalias attribute to LLVM. noalias means the pointed data cannot be accessed by other code, which means:
    • It allows aggressively merging reads. Before next write to it, it can be temporarily treated as constant.
    • It allows aggressively merging writes. If there are two memory writes to it, compiler can remove the first write, only keep the last write.
    • It allows removing reads after write, using the previous write as read result.
    • It allows aggressively reordering reads/writes to it between other computation and other memory accesses.
    • The above give compiler a lot of freedom of transforming code, which enables many other optimizations.
    • Without noalias, the optimizer must consider all possible reads/writes to the same value to do above transformation. In many cases, compiler don't have enough information, so much fewer optimizations can be done.

Interior mutability summary​

Mutable borrow exclusiveness is overly restrictive. It is not necessary for memory safety in single-threaded code when not using interior pointer. There is interior mutability that allows getting rid of that constraint.

Interior mutability allows you to mutate something from an immutable reference to it. (Because of that, immutable borrow doesn't necessarily mean the pointed data is actually immutable. This can cause some confusion.)

Ways of interior mutability:

  • Cell<T>. It's suitable for simple copy-able types like integer. In the previous contagious borrow example, if the total_score is replaced with Cell<u32> then mutating it doesn't need mutable borrow of parent thus avoid the issue. Cell<T> only supports replacing the whole T at once, and doesn't support getting a mutable borrow.
  • RefCell<T>, suitable for data structure that does incremental mutation, in single-threaded cases. It has internal counters tracking how many immutable borrow and mutable borrow currently exist. If it detects violation of mutable borrow exclusiveness, .borrow() or .borrow_mut() will panic.It can cause crash if there is nested borrow that involves mutation.
  • Mutex<T> RwLock<T>, for locking in multi-threaded case. Its functionality is similar to RefCell. Note that unnecessary locking can cost performance, and has risk of deadlock. It's not recommended to overuse Arc<Mutex<T>> just because it can satisfy the borrow checker.
  • QCell<T>. Elaborated below.
  • Atomic types such as AtomicU32
  • UnsafeCell<T>
  • Lazily-initialized OnceCell<T>
  • ......

They are usually used inside reference counting (Arc<...>, Rc<...>).

RefCell is not panacea​

In the previous contagious borrow case, wrapping parent in RefCell<> can make the code compile. However it doesn't fix the issue. It just turns compile error into runtime panic:

use std::cell::RefCell;  
pub struct Parent { total_score: u32,  children: Vec<Child> }  
pub struct Child { score: u32 }  
impl Parent {  
    fn get_children(&self) -> &Vec<Child> {  
        &self.children  
    }  
    fn add_score(&mut self, score: u32) {  
        self.total_score += score;  
    }  
}  
fn main() {  
    let parent: RefCell<Parent> = RefCell::new(Parent{total_score: 0, children: vec![Child{score: 2}]});  
    for child in parent.borrow().get_children() {  
        parent.borrow_mut().add_score(child.score);  
    }  
}

It will panic with RefCell already borrowed error.

RefCell still follows mutable borrow exclusiveness rule, just checked at runtime, not compile time. Borrowing one fields inside RefCell still borrows the whole RefCell.

Wrapping parent in RefCell cannot fix contagious borrow, but putting individual children into RefCell can work, as it makes borrow more fine-grained.

See also: Dynamic borrow checking causes unexpected crashes after refactorings

Rust assumes that, if you have a mutable borrow &mut T, you can use it at any time. But holding the reference is different to using reference. There are use cases that I have two mutable references to the same object, but I only use one at a time. This is the use case that RefCell solves.

Another problem: It's hard to return a reference borrowed from RefCell.

As the previous example can be fixed by Cell, without RefCell, here is another contagious borrow example:

use std::collections::HashMap;  
pub struct Parent {  
    entries: HashMap<String, Entry>,  
    passed_names: Vec<String>  
}  
pub struct Entry {  score: u32  }  
impl Parent {  
    fn get_entries(&self) -> &HashMap<String, Entry> {  
        &self.entries  
    }  
    fn add_name(&mut self, name: &str) {  
        self.passed_names.push(name.to_string());  
    }  
}  
fn main() {  
    let mut map: HashMap<String, Entry> = HashMap::new();  
    map.insert("a".to_string(), Entry { score: 100 });  
    let mut parent = Parent {  
        entries: map, passed_names: vec![]  
    };  
    for (name, entry) in parent.get_entries() {  
        if (entry.score > 20) {  
            parent.add_name(name);  
        }  
    }  
}

Compile error

22 |     for (name, entry) in parent.get_entries() {
   |                          --------------------
   |                          |
   |                          immutable borrow occurs here
   |                          immutable borrow later used here
23 |         if (entry.score > 20) {
24 |             parent.add_name(name);
   |             ^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

Then let's try to fix it using RefCell. As previously mentioned, wrapping Parent in RefCell doesn't work. We need to wrap two fields of parent into RefCell:

pub struct Parent {  
    entries: RefCell<HashMap<String, Entry>>,  
    passed_names: RefCell<Vec<String>>  
}  
pub struct Entry {  score: u32  }  
impl Parent {  
    fn get_entries(&self) -> &HashMap<String, Entry> {  
        self.entries.borrow()  
    }  
    fn add_name(&self, name: &str) {  
        self.passed_names.borrow_mut().push(name.to_string());  
    }  
}

But returning a borrow from RefCell is not that simple:

error[E0308]: mismatched types
  --> src\main.rs:10:9
   |
9  |     fn get_entries(&self) -> &HashMap<String, Entry> {
   |                              ----------------------- expected `&HashMap<String, Entry>` because of return type
10 |         self.entries.borrow()
   |         ^^^^^^^^^^^^^^^^^^^^^ expected `&HashMap<String, Entry>`, found `Ref<'_, HashMap<String, Entry>>`
   |
   = note: expected reference `&HashMap<_, _>`
                 found struct `Ref<'_, HashMap<_, _>>`
help: consider borrowing here
   |
10 |         &self.entries.borrow()
   |         +

Because the borrow got from RefCell is not normal borrow, it's actually Ref. Ref implements Deref so it can be used similar to a normal borrow.

The "help: consider borrowing here" suggestion won't solve the compiler error. Don't blindly follow compiler's suggestions.

Possible solutions (all not recommended):

  1. Return a Ref<HashMap<String, Entry>>.
  2. Return &RefCell<HashMap<String, Entry>>.
  3. Return impl Deref<Target=HashMap<String, Entry>>. It's existential type, not concrete type.
  4. Make the field Rc<RefCell<...>> and return cloned Rc.

In 1,2,4, the types related to RefCell is exposed in function signature. Cannot change RefCell to another things (e.g. RwLock) without changing function signature.

In 3, the function signature has no RefCell-related type, but it's existential type and can lead to other issues (e.g. its type cannot be written out in local variable).

Only in 4, can the returned reference be stored for long time.

All the 4 solutions are all not recommended (only use when really necessary).

Rc<RefCell<...>> and Arc<Mutex<...>> are not panacea​

Rc<RefCell<...>> and Arc<Mutex<...>> allows freely copying reference and freely mutating things, just like in other languages. Finally "get rid of shackle of borrow checker". However, there are traps:

  • Contagious borrowing. As previously mentioned, RefCell doesn't solve contagious borrowing. Mutex also won't. Violating mutable borrow exclusiveness in the same thread is panic (or error) in RefCell and deadlock in Mutex. Rust lock is not re-entrant, explained below.
  • Need to cut cycle using Weak, unless it will memory leak.
  • Performance. Rc and RefCell has relatively small performance cost. But unnecessary locking can hurt performance. Arc also can have performance issue, explained below. It's still ok to use them when not in performance bottleneck.
  • Their syntax ergonomic is not good. The code will have a lot of "noise" like .borrow().borrow_mut().

QCell​

QCell<T> has an internal ID. QCellOwner is also an ID. You can only use QCell via an QCellOwner that has matched ID.

The borrowing to QCellOwner "centralizes" the borrowing of many QCells associated with it, ensuring mutable borrow exclusiveness. Using it require passing borrow of QCellOwner in argument everywhere it's used.

QCell will fail to borrow if the owner ID doesn't match. Different to RefCell, if owner ID matches, it won't panic just because nested borrow.

Its runtime cost is low. When borrowing, it just checks whether cell's id matches owner's id. It has memory cost of owner ID per cell.

One advantage of QCell is that the duplicated borrow will be compile-time error instead of runtime panic, which helps catch error earlier. If I change the previous RefCell panic example into QCell:

pub struct Parent { total_score: u32, children: Vec<Child> }
pub struct Child { score: u32 }
impl Parent {
    fn get_children(&self) -> &Vec<Child> { &self.children }
    fn add_score(&mut self, score: u32) { self.total_score += score; }
}
fn main() {
    let owner: QCellOwner = QCellOwner::new();
    let parent: QCell<Parent> = QCell::new(&owner, Parent{total_score: 0, children: vec![Child{score: 2}]});
    for child in parent.ro(&owner).get_children() {
        parent.rw(&mut owner).add_score(child.score);
    }
}

Compile error:

17 |     for child in parent.ro(&owner).get_children() {
   |                  --------------------------------
   |                  |         |
   |                  |         immutable borrow occurs here
   |                  immutable borrow later used here
18 |         parent.rw(&mut owner).add_score(child.score);
   |                   ^^^^^^^^^^ mutable borrow occurs here

It turns runtime panic into compile error, which make discovering problems eariler.

GPUI's Model<T> is similar to Rc<QCell<T>>, where GPUI's AppContext correspond to QCellOwner.

It can also work in multithreading, by having RwLock<QCellOwner>. This can allow one lock to protect many pieces of data in different places 7.

Ghost cell and LCell are similar to QCell, but use closure lifetime as owner id. They are zero-cost, but more restrictive (owner is tied to closure scope, cannot dynamically create, owner cannot outlive closure).

Rust lock is not re-entrant​

Re-entrant lock means one thread can lock one lock, then lock it again, then unlock twice, without deadlocking. Rust lock is not re-entrant. (Rust lock is also responsible for keeping mutable borrow exclusiveness. Allowing re-entrant can produce two &mut for same object.)

For example, in Java, the two-layer locking doesn't deadlock:

public class Main {  
    public static void main(String[] args) {  
        Object lock = new Object();  
        synchronized (lock) {  
            synchronized (lock) {  
                System.out.println("within two layers of locking");  
            }  
        }  
        System.out.println("finish");  
    }  
}

But in Rust the equivalent will deadlock:

fn main() {  
    let mutex: Mutex<u64> = Mutex::new(0);  
    {  
        let mut g1: MutexGuard<u64> = mutex.lock().unwrap();  
        {  
            println!("going to do second-layer lock");  
            let mut g2 = mutex.lock().unwrap();  
            println!("within two layers of locking");  
        }  
    }  
    println!("finish");  
}

It prints going to do second-layer lock then deadlocks.

In Rust, it's important to be clear about which scope holds lock. Golang lock is also not re-entrant.

Another important thing is that Rust only unlocks at the end of scope by default. mutex.lock().unwrap() gives a MutexGuard<T>. MutexGuard implements Drop, so it will drop at the end of scope. It's different to the local variables whose type doesn't implement Drop, they are dropped after their last use (unless borrowed). This is called NLL (non-lexical lifetime).

Just clone the data​

For example, if borrow checker has trouble with a string borrowing, you can just clone the string. It's usually fine as long as it's not performance bottleneck.

Arc is not always fast​

Arc uses atomic operations to change its reference count. (Cloning and dropping Arc changes reference count, but borrowing Arc doesn't.)

However, when many threads frequently change the same atomic counter, performance can degrade. The more threads touching it, the slower it is.

Modern CPUs use cache coherency protocol (e.g. MOESI). Atomic operations often require the CPU core to hold "exclusive ownership" to cache line (this may vary between different hardware). Many threads frequently doing so cause cache contention, similar to locking, but on hardware.

Example 1, Example 2

Atomic reference counting is still fast if not contended (mostly only one thread change reference count). Atomic reference counting is faster on Apple silicon than Intel CPUs. 8

Solutions:

  • Avoid sharing the same reference count. Copying data is sometimes better.
  • trc and hybrid_rc. They use per-thread non-atomic counter, and another shared atomic counter for how many threads use it. This can make atomic operations be less frequent, getting higher performance.
  • For scenario of frequent short-term reads:

These deferred memory reclamation techniques (hazard pointer, epoch-based) are also used in lock-free data structures. If one thread can read an element while another thread removes and frees the same element in parallel, it will not be memory-safe (this issue doesn't exist in GC languages).

Reference counting vs tracing GC​

There are some ambiguity of the word "GC". Some say reference counting is GC, some say it isn't.

No matter what the definition of "GC" is, reference counting is different from tracing GC (in Java/JS/C#/Golang/etc.):

Reference countingTracing GC
Frees memory immediatelyFrees in deferred and batched way 9
Freeing a whole large structure may cause large lag 10Require more memory to achieve high performance, otherwise GC lag will be large.
Finds greatest fixed pointFinds least fixed point
Propagates "death". (freeing one object may cause its children to be freed)Propagates "live". (a living object cause its children to live, except for weak reference)
Cloning and dropping a reference involves atomic operation (except single-threaded Rc)Reading/writing an on-heap reference may involve read/write barrier (often a branch, no atomic memory access)
Cannot automatically handle cycles. Need to use weak reference to cut cycleCan handle cycles automatically
Cost is roughly O(reference count changing frequency) 11Cost is roughly O(count of living objects * GC frequency) 12

Bump allocator​

bumpalo provides bump allocator. In bump allocator, allocation is fast because it usually just increase an integer. It supports quickly freeing the whole arena, but doesn't support freeing individual objects.

It's usually faster than normal memory allocators. Normal memory allocator will do a lot of bookkeeping work for each allocation and free. Each individual memory region can free separately, these regions can be reused for later allocation, these information need to be recorded and updated.

Bump allocator frees memory in batched and deferred way, which is similar to tracing GC. As it cannot free individual objects, it may temporarily consume more memory, similar to tracing GC.

Bump allocator is suitable for temporary objects, where you are sure that none of these temporary objects will be needed after the work complets.

The function signature of allocation (changed for clarity):

impl Bump {
    ...
    pub fn alloc<T, 'bump>(&'bump self, val: T) -> &'bump mut T { ... }
}

It takes immutable borrow of Bump (it has interior mutability). It moves val into the bump-allocated memory region. It outputs a mutable borrow, having the same lifetime as bump allocator. That lifetime ensures memory safety (cannot make the borrow of allocated value outlive bump allocator).

If you want to keep the borrow of allocated result for long time, then lifetime annotation is often required. In Rust, lifetime annotation is also contagious:

  • Every struct that holds bump-allocated borrow need to also have lifetime annotation of the bump allocator.
  • Every function that use it also needs lifetime annotation. Rust has lifetime elision, which allows you to omit lifetime in function signature in some cases. However it doesn't work in all cases.

Adding or removing lifetime for one thing may involve refactoring many code that use it, which can be huge work. Be careful in planning what lifetime parameters it needs.

Bump doesn't implement Sync, so &Bump is not Send. It cannot be shared across threads (even if it can share, there will be lifetime constraint that force you to use structured concurrency). It's recommended to have separated bump allocator in each thread, locally.

Using unsafe​

By using unsafe you can freely manipulate pointers and are not restricted by borrow checker. But writing unsafe Rust is harder than just writing C, because you need to carefully avoid breaking the constraints that safe Rust code relies on. A bug in unsafe code can cause issue in safe code.

Writing unsafe Rust correctly is hard. Here are some traps in unsafe:

  • Don't violate mutable borrow exclusiveness.
    • A &mut cannot overlap with any other borrow that overlaps.
    • The overlap here also includes interior pointer. A &mut to an object cannot co-exist with any other borrow into any part of that object.
    • Violating that rule cause undefined behavior and can cause wrong optimization. Rust adds noalias attribute for mutable borrows into LLVM IR. LLVM will heavily optimize based on noalias. See also
    • The above rule doesn't apply to raw pointer *mut T.
    • It's very easy to accidentally violate that rule when using borrows in unsafe. It's recommended to always use raw pointer and avoid using borrow (including slice borrow) in unsafe code. Related1, Related2
  • Pointer provenance.
    • Two pointers created from two provenances is considered to never alias. If their address equals, it's undefined behavior.
    • Converting an integer to pointer gets a pointer with no provenance, which is undefined behavior, unless the integer was converted from a pointer.
    • Adding a pointer with an integer doesn't change provenance.
  • Using uninitialized memory is undefined behavior. MaybeUninit
  • a = b will drop the original object in place of a. If a is uninitialized, then it will drop an unitialized object, which is undefined behavior. Use addr_of_mut!(...).write(...) Related
  • Handle panic unwinding.
  • Reading/writing to mutable data that's shared between threads need to use atomic or volatile access (read_volatile, write_volatile). If not, optimizer may wrongly merge and reorder reads/writes. Note that volatile access themself doesn't establish memory order (unlike Java volatile).
  • ......

Modern compilers tries to optimize as much as possible. To optimize as much as possible, the compiler makes assumptions as much as possible. Breaking any of these assumption can lead to wrong optimization. That's why it's so complex. See also

Unfortunately Rust's syntax ergonomics on raw pointer is currently not good:

  • If p is a raw pointer, you cannot write p->field (like in C/C++), and can only write (*p).field
  • Raw pointer cannot be method receiver (self).
  • There is no "raw pointer to slice". You need to manually .add() pointer and dereference. Bound checking is also manual.

Contagious borrowing in container​

Mutably borrow one element in Vec disallow borrowing of other elements. Workaround is split_at_mut.

For HashMap, use get_disjoint_mut. (There seem to be no such thing in BTreeMap.)

Contagious borrowing between branches​

Current borrow checker does coarse-grained analysis on branch. One branch's output's borrowing is contagious to another branch.

Currently, this won't compile (see also):

fn get_default<'r, K: Hash + Eq + Copy, V: Default>(
    map: &'r mut HashMap<K, V>,
    key: K,
) -> &'r mut V {
    match map.get_mut(&key) { // -------------+ 'r
        Some(value) => value,              // |
        None => {                          // |
            map.insert(key, V::default()); // |
            //  ^~~~~~ ERROR               // |
            map.get_mut(&key).unwrap()     // |
        }                                  // |
    }                                      // |
}

Becaue the first branch Some(value) => ...'s output value indirectly mutably borrows map, the second branch has to also indirectly mutably borrow map, which conflicts with another mutable borrow in scope.

This will be fixed by Polonius borrow checker. Currently (2025 Aug) it's available in nightly Rust and can be enabled by an option.

Send and Sync​

Rust favors tree-shaped ownership. Each object is owned by exactly one place. If you send tree-shaped data to another thread, only one thread can access it, so it's thread-safe. No data race.

Sending an immutable borrow to another thread is also fine as long as the shared data is actually immutable.

But there are exceptions. One exception is interior mutability. Because of interior mutability, the data pointed by immutable borrow &T may no longer actually be immutable. So Rust prevents sharing &Cell<T> and &RefCell<T> by making Cell<T> and RefCell<T> not Sync. If X is Sync then &X is Send. If X is not Sync then &X is not Send. This prevents Cell and RefCell from being shared across threads.

Rc also has internal shared mutable reference counter. It's not atomic, so Rc cannot be passed between threads. It's neither Send or Sync.

But &Mutex<T> can be shared because lock protects them. Also immutable reference to atomic cells like &AtomicU32 can be shared because of atomicity. Mutex<T> and AtomicU32 are Sync so &Mutex<T> and &AtomicU32 are Send.

There are things that are Sync but not Send, like MutexGuard. If something is already locked, sharing its reference to other threads temporarily is fine. But moving a MutexGuard to another thread is not fine because locking is tied to thread.

When using async runtime​

Tokio is a popular async runtime.

In Tokio, submitting a task require the future to be Send and 'static.

pub fn spawn<F>(future: F) -> JoinHandle<F::Output>  
where  
    F: Future + Send + 'static,  
    F::Output: Send + 'static,

It requires the future need to be Send and 'static:

  • 'static means it's standalone (self-owned). It doesn't borrow temporary things. It can borrow global values (global values will always live when program is running). It cannot borrow a value that only temporarily exists.

    If the future need to share data with outside, pass Arc<T> into (not &Arc<T>).

    Note that the "static" in C/C++/Java/C# often mean global variable. But in Rust its meaning is different.

  • Send means that the future can be sent across threads. Tokio use work-stealing, which means that one thread's task can be stolen by other threads that currently have no work.

Another important trap is that, the normal sleep std::thread::sleep and normal locking std::sync::Mutex should not be used when using async runtime, because they block using OS functionality without telling async runtime, so they will block the async runtime's scheduling thread. In Tokio, use tokio::sync::Mutex and tokio::time::sleep.

Side effect of extracting and inlining variable​

In C and GC languages:

  • If a variable is used only once, you can inline that variable. This will only change execution order (except in short-circuit 13).
  • Extracting a variable will only change execution order (except when variable is used twice or in short-circuit).

But in Rust it's different.

Lifetime of temporary value​

  • A temporary value drops immediately after evaluating, except when there is a borrow to it, its lifetime extends by the borrow. It's called temporary lifetime extension.
    • There are implicit ways of creating borrow. DeRef can implicitly borrow, a.b() can implicitly borrow a
    • match, if let or while let can also borrow which extend the lifetime
    • Sometimes temporary lifetime extension doesn't work, such as let guard = Mutex::new(0).lock().unwrap();
  • A value that's put into a local variable:
    • If its type implements Drop, then it will drop at the end of scope (one example is MutexGuard).
    • If its type doesn't implement Drop, then it will drop after its last use. This is called NLL (non-lexical lifetime).

Simplify:

  • Putting a temporary value to local variable usually make it live longer.
  • Inlining a local variable usually make it live shorter.

Reborrow​

Normally mutable borrow &mut T can only be moved and cannot be copied.

But reborrow is a feature that sometimes allow you to use a mutable borrow multiple times. Reborrow is very common in real-world Rust code. Reborrow is not explicitly documented. See also

Example:

fn mutate(i: &mut u32) -> &mut u32 {  
    *i += 1;  
    i  
}  
fn mutate_twice(i: &mut u32) -> &mut u32 {  
    mutate(i);  
    mutate(i)  
}

That works. Rust will implicitly treat the first mutate(i) as mutate(&mut *i) so that i is not moved into and become usable again.

But extracting the second i into a local variable early make it not compile:

fn mutate_twice(i: &mut u32) -> &mut u32 {  
    let j: &mut u32 = i;  
    mutate(i);  
    mutate(j)  
}
7  | fn mutate_twice(i: &mut u32) -> &mut u32 {
   |                    - let's call the lifetime of this reference `'1`
8  |     let j: &mut u32 = i;
   |                       - first mutable borrow occurs here
9  |     mutate(i);
   |            ^ second mutable borrow occurs here
10 |     mutate(j)
   |     --------- returning this value requires that `*i` is borrowed for `'1`

Move cloned data into closure​

tokio::spawn require future to be standalone and doesn't borrow other things ('static).

Passing passing an Arc (that's used later) into moved closure makes closure borrow the Arc. The data that contains borrow is not standalone (not 'static).

#[tokio::main]  
async fn main() {  
    let data: Arc<u64> = Arc::new(1);  
  
    let task1_handle = tokio::spawn(async move {  
        println!("From task: Data: {}", *data);  
    });  
  
    println!("From main thread: Data: {}", *data);  
}

Compile error

6    |     let data: Arc<u64> = Arc::new(1);
     |         ---- move occurs because `data` has type `Arc<u64>`, which does not implement the `Copy` trait
7    |
8    |     let task1_handle = tokio::spawn(async move {
     |                                     ---------- value moved here
9    |         println!("From task: Data: {}", *data);
     |                                          ---- variable moved due to use in coroutine
...
12   |     println!("From main thread: Data: {}", *data);
     |                                             ^^^^ value borrowed here after move

Manually clone the Arc<T> and put it into local variable works. It will make the cloned version to move into future:

#[tokio::main]  
async fn main() {  
    let data: Arc<u64> = Arc::new(1);  
  
    let data2 = data.clone(); // this is necessary
    let task1_handle = tokio::spawn(async move {  
        println!("From task: Data: {}", *data2);  
    });  
  
    println!("From main thread: Data: {}", *data);  
}

Note that inlining data2 local variable make it not compile:

#[tokio::main]  
async fn main() {  
    let data: Arc<u64> = Arc::new(1);  
    let task1_handle = tokio::spawn(async move {  
        println!("From task: Data: {}", *data.clone());  
    });  
    println!("From main thread: Data: {}", *data);  
}
5    |     let data: Arc<u64> = Arc::new(1);
     |         ---- move occurs because `data` has type `Arc<u64>`, which does not implement the `Copy` trait
6    |     let task1_handle = tokio::spawn(async move {
     |                                     ---------- value moved here
7    |         println!("From task: Data: {}", *data.clone());
     |                                          ---- variable moved due to use in coroutine
8    |     });
9    |     println!("From main thread: Data: {}", *data);
     |                                             ^^^^ value borrowed here after move

There is a proposal on improving syntax ergonomic of it.

Summarize the contagious things​

  • Borrowing that cross function boundary is contagious. Just borrowing a wheel of car can indirectly borrow the whole car.
  • Mutate-by-recreate is contagious. Recreating child require also recreating parent that holds the new child, and parent's parent, and so on.
  • Lifetime annotation is contagious. If some type has a lifetime parameter, then every type that holds it must also have lifetime parameter. Every function that use them also need lifetime parameter, except when lifetime elision works. Refactoring that adds/remove lifetime parameter can be huge work.
  • In current borrow checker, one branch's output's borrowing is contagious to the whole branching scope.
  • async is contagious. async function can call normal function. Normal function cannot easily call async function (but it's possible to call by blocking).
  • Being not Sync/Send is contagious. A struct that indirectly owns a non-Sync data is not Sync. A struct that indirectly owns a non-Send data is not Send.
  • Error passing is contagious. If panic is not acceptable, then all functions that indirectly call a fallible function must return Result. Related: NaN is contagious in floating point computaiton.

Rust is a tradeoff​

As commonly mentioned, Rust gives memory safety, thread safety and opportunity of high performance.

Rust also helps preventing bugs other than memory safety and thread safety:

  • Algebraic data type (e.g. Option, Result) helps avoid creating illegal data from the source. Using ADT data require pattern match all cases, avoiding forgetting handling one case. (except when using escape hatch like unwrap()).
  • Mutable borrow exclusiveness prevents iterator invalidation.
  • Explicit .clone() avoids accidentally copying string like in C++.
  • ......

Not all security issues are memory-safety issue. According to Common Weakness Enumeration 2024 Top 25 Most Dangerous Software Weaknesses, many real-world vulnerabilities are XSS, SQL injection, directory traversal, command injection, missing authentication, etc. that are not memory safety. The GC languages are also memory-safe 14, but there are still vulnerabilities in Java (e.g. Log4j vulnerability).

Rust prefers data-oriented design. Rust doesn't fit OOP. Rust dislikes sharing mutable data. Rust dislikes circular reference. Getter and setter can easily cause contagious borrow issue. Sharing and mutation has many limitations.

Rust is less flexible and does not suit quick iteration. A new requirement often require changing reference structure, which often involve large refactoring in Rust.

Rust saves time of debugging memory safety issue and thread safety issue. Many memory safety issues and thread safety issues are random. Random bugs are not easy to reproduce and debug. In a complex and unfamiliar codebase, debugging a random bug may take weeks or months. Rust greatly saves debugging time in this aspect.

Footnotes​

  1. The native Rust ownership relation form a tree. Reference counting (Rc, Arc) allows shared ownership. ↩

  2. Note that here "reference" here means reference in general OOP context (where there is no distinction between ownership and non-owning reference, think about reference in Java/C#/JS/Python). This is different to the Rust reference. I will use "borrow" for Rust reference in this article. ↩

  3. This simplified code example is just for illustrating contagious borrow issue. The total score doesn't need to be a mutable field. It's analogous to a complex state that will exist in real applications. Same for other examples. ↩

  4. Specifically, Gödel encodes symbols, statements and proofs into integer, called Gödel number. There exists many ways of encoding symbols/statements/proofs as data, and which exact way is not important. For simplicity, I will treat them all as data, and ignore the conversion between data and symbol/statements/proofs. ↩

  5. Here x(x) is symbol substitution. replacing the free variable x with x, while avoid making two different variables same name by renaming when necessary. It's also similar to Y combinator: Y = f -> (x -> f(x(x))) (x -> f(x(x))). In that case f = unprovable, H = x -> f(x(x)), Y(f) = H(H), Y(f) is a fixed point of f: f(Y(f)) = Y(f). G = Y(f), f(G) = G ↩

  6. Each slotmap ensures key uniqueness, but if you mix keys of different slotmaps, the different keys of different slotmap may duplicate. Using the wrong key may successfully get an element but logically wrong. ↩

  7. Sometimes, having fine-grained lock is slower because of more lock/unlock operations. But sometimes having fine-grained lock is faster because it allows higher parallelism. Sometimes fine-grained lock can cause deadlock but coarse-grained lock won't deadlock. It depends on exact case. ↩

  8. See also. That was in 2020. Unsure whether it changed now. One possible reason is that ARM allows weaker memory order than X86. Also, Swift and Objective-C use reference counting almost everywhere, so possibly Apple payed more efforts in optimizing atomic reference counting. ↩

  9. Tracing GC is faster for short-lived programs (such as some CLI programs and serverless functions), because there's no need to free memory for individual objects on exit. Example: My JavaScript is Faster than Your Rust. The same optimization is also achievable in Rust, but require extra work (e.g. mem::forget, bump allocator). ↩

  10. It lags because it need to do many counter decrement and deallocation for each individual object. Can be workarounded by sending the Arc to another thread and drop in that thread. Also, for deep structures, dropping may stack overflow. ↩

  11. Contended atomic operations (many threads touch one atomic value at the same time) are much slower than when not contended. Its cost also include memory block allocation and freeing. ↩

  12. GC frequency is roughly porpotional to allocation speed divide by free memory. In generational GC, a minor GC only scans young generation, whose cost is roughly count of living young generation objects. But it still need to occasionally do full GC. ↩

  13. a() || b() will not execute b() if a() returns true. a() && b() will not execute b() if a() returns false. ↩

  14. Note that Golang is not fully memory-safe under data race. For example, string in Golang is 16 bytes, 8-byte pointer and 8-byte length. Tearing can cause pointer to mismatch length, prone out-of-bound read. ↩

Tags:
Last updated on by qouteall